package offer;

/**
 * @author SSK
 */
public class T40 {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
    public boolean IsBalanced_Solution(TreeNode root) {
        if (IsBalanced(root)<0) {
            return false;
        } else {
            return true;
        }
    }
    public int IsBalanced(TreeNode root) {
        if (root==null) {
            return 0;
        }
        int left = 0;
        int right = 0;
        left = IsBalanced(root.left);
        right = IsBalanced(root.right);
        if (Math.abs(left-right)>1||left<0||right<0) {
            return Integer.MIN_VALUE;
        }
        return Math.max(left , right) + 1;
    }
    public void test() {
        TreeNode[] treeNodes = new TreeNode[8];
        for (int i = 0; i < 7; i++) {
            treeNodes[i] = new TreeNode(i);
        }
        treeNodes[1].left = treeNodes[2];
        treeNodes[1].right = treeNodes[3];
        treeNodes[2].left = treeNodes[4];
        treeNodes[2].right = treeNodes[5];
        treeNodes[3].left = treeNodes[6];
        treeNodes[3].right = treeNodes[7];
        System.out.println(IsBalanced_Solution(treeNodes[1]));
    }
    public static void main ( String[] args) {

        new T40().test();
    }
}
